package tree.ntree;

import java.util.*;

/**
 * n叉树层序遍历
 */
public class NForkTreeSequenceTraversal {

    static class TreeNode {

        int val;

        List<TreeNode> children = new ArrayList<>();

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        int[] input = new int[] {1,-1,3,2,4,-1,5,6};
        TreeNode root = buildTreeFromArray(input);
        List<List<Integer>> result = sequenceTraversal(root);
        System.out.println(result);
    }

    private static TreeNode buildTreeFromArray(int[] input) {
        if (input == null || input.length == 0) {
            return null;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(input[0]);
        queue.offer(root);

        for (int i = 1; i < input.length; i++) {
            TreeNode parent = queue.peek(); // 获取当前父节点而不将其从队列中移除
            if (input[i] != -1) {
                TreeNode child = new TreeNode(input[i]);
                if (parent != null) {
                    parent.children.add(child); // 将新节点添加到当前父节点的子节点中
                }
                queue.offer(child);
            } else {
                queue.poll(); // 如果 input[i] == -1，从队列中移除当前父节点
            }
        }
        return root;
    }

    private static List<List<Integer>> sequenceTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 获取当前层节点个数
            int size = queue.size();
            List<Integer> curr = new ArrayList<>();
            // 遍历当前层的节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node != null) {
                    curr.add(node.val);
                    // 加入孩子节点到队列中
                    node.children.forEach(queue::offer);
                }
            }
            result.add(curr);
        }
        return result;
    }
}
